// 可持久化线段树 历史区间最值
// https://soj.turingedu.cn/problem/60900/
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int maxn = 5 + 1e4;
const int max_size = 5 + 2 * maxn + 1e5 * 16;

int n, m;
int a[maxn];
int tot;
int val[max_size], ch[max_size][2];

int new_node(int x) {
    val[++tot] = x, ch[tot][0] = 0, ch[tot][1] = 0;
    return tot;
}

inline void merge(int now) {
    val[now] = max(val[ch[now][0]], val[ch[now][1]]);
}

int cp(int now) {
    val[++tot] = val[now], ch[tot][0] = ch[now][0], ch[tot][1] = ch[now][1];
    return tot;
}

int build(int l, int r) {
    if (l == r) return new_node(a[l]);
    int now = new_node(0), mid = l + r >> 1;
    ch[now][0] = build(l, mid);
    ch[now][1] = build(mid + 1, r);
    merge(now);
    return now;
}

int update(int now, int l, int r, int i, int x) {
    now = cp(now);
    if (l == r) {
        val[now] = x;
        return now;
    }

    int mid = l + r >> 1;
    if (i <= mid)
        ch[now][0] = update(ch[now][0], l, mid, i, x);
    else
        ch[now][1] = update(ch[now][1], mid + 1, r, i, x);

    merge(now);
    return now;
}

int ask(int now, int l, int r, int s, int t) {
    if (s <= l && r <= t) return val[now];
    int mid = l + r >> 1;
    if (t <= mid) return ask(ch[now][0], l, mid, s, t);
    if (s > mid) return ask(ch[now][1], mid + 1, r, s, t);
    return max(ask(ch[now][0], l, mid, s, t), ask(ch[now][1], mid + 1, r, s, t));
}

int root[max_size], rsiz;

int main() {
    n = rad();
    int Q = rad();
    rf(i, n) a[i] = rad();
    root[++rsiz] = build(1, n);
    rf(q, Q) {
        int op = rad();
        if (op == 0) {
            int k = rad(), l = rad(), r = rad();
            printf("%d\n", ask(root[k], 1, n, l, r));
        } else if (op == 1) {
            int k = rad(), i = rad(), x = rad();
            root[++rsiz] = update(root[k], 1, n, i, x);
        }
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}